function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

function insertNode(root, val) {
    var p = root;
    while (p) {
        if (val < p.val) {
            if (p.left) {
                p = p.left;
            } else {
                p.left = new TreeNode(val);
                break;
            }
        } else {
            if (p.right) {
                p = p.right;
            } else {
                p.right = new TreeNode(val);
                break;
            }
        }
    }
}

function preOrderTraverse(trees) {
    if (!trees) return;
    console.log(trees.val);
    preOrderTraverse(trees.left);
    preOrderTraverse(trees.right);
}

function inOrderTraverse(trees) {
    if (!trees) return;
    inOrderTraverse(trees.left);
    console.log(trees.val);
    inOrderTraverse(trees.right);
}

function postOrderTraverse(trees) {
    if (!trees) return;
    postOrderTraverse(trees.left);
    postOrderTraverse(trees.right);
    console.log(trees.val);
}

//非递归遍历
function inOrderTraverseNoRecursion(trees) {
    var stack = [];
    var p = trees;
    while (p || stack.length > 0) {
        while (p) {
            stack.push(p);
            p = p.left;
        }

        p = stack.pop();
        console.log(p.val);
        p = p.right;

        // if(p.right){
        //     stack.push(p);
        //     p = p.right;
        // }else{
        //     p = stack.pop();
        // }
        //p = stack.pop();
    }
}
//前序遍历序列化 [1,2,3,null,null,4,5]
var serialize1 = function (root) {
    var stack = [];
    var p = root;
    while (p || stack.length > 0) {
        while (p) {
            console.log(p.val);
            stack.push(p);
            p = p.left;
        }

        p = stack.pop(p);
        p = p.right;
    }
};
var serialize = function (root) {
    var ret = [];
    var stack = [];
    var p = root;
    while (p || stack.length > 0) {
        while (p) {
            console.log(p.val);
            ret.push(p.val);
            stack.push(p);
            p = p.left;
        }
        ret.push('#');
        p = stack.pop(p);
        p = p.right;
    }
    ret.push('#');

    return ret.join(',');
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var rdeserialize = function (arr) {
    if (arr.length == 0) return null;
    if (arr[0] === '#') {
        arr.splice(0, 1);
        return null;
    }
    var root = new TreeNode(arr[0]);
    arr.splice(0, 1);
    root.left = rdeserialize(arr);
    root.right = rdeserialize(arr);
    return root;
}
var deserialize = function (data) {
    // var arr = JSON.parse(data);
    var arr = data.split(',');
    return rdeserialize(arr);
};

(function test() {
    var arr = [50, 40, 100, 200, 10, 12, 11, 9, 99, 55];
    var root = new TreeNode(arr[0]);
    for (var i = 1; i < arr.length; i++) {
        insertNode(root, arr[i]);
    }
    // preOrderTraverse(root);
    console.log("*****");
    inOrderTraverse(root);
    console.log("*****");
    // postOrderTraverse(root);

    inOrderTraverseNoRecursion(root);
    console.log("%%%%%%%%%%%%%%");

    var newRoot = new TreeNode(1);
    newRoot.left = new TreeNode(2);
    newRoot.right = new TreeNode(3);
    newRoot.right.left = new TreeNode(4);
    newRoot.right.right = new TreeNode(5);
    console.log(serialize(newRoot));
    console.log(deserialize("1,2,#,#,3,4,#,#,5,#,#"));

})();